#!/usr/bin/env python
import math,sys,pickle,util
from pympler.classtracker import ClassTracker

from pympler import summary
#===============================================================================
# bucket : (value, prev, next, elements)
#===============================================================================


class HashSummary :
	def __init__(self,k):
		self.delete_bucket_count = 0
		self.get_min_count = 0;
		self.buckets = {} 	# dict : bucket value -> bucket
		self.elements = {} 	# dict : element_id -> bucket value
		self.k = k # size of SpaceSaving
		self.min_bucket = None # value of minimum bucket

	def add_item(self,item):
		key = int( math.ceil(item[1]) )
		#print "add_item. ", item
		ss_item = (item[0],item[1],0.0)
		#if not self.elements.has_key(item[0]) :
		#print "! in els"
		if len(self.buckets) == 0 :
			#print "empty bcejkts "
			self.buckets[key] = [key,-1, -1,{item[0]:ss_item}]
			self.elements[item[0]] = key
			self.min_bucket = key
		elif key not in self.buckets :
			#print "new key not in buckets"
#				_key =  self.min_bucket
			_bucket = self.buckets[self.min_bucket]
			while _bucket[2] != -1 and _bucket[2] < key :
				_bucket = self.buckets[_bucket[2]]

			self.buckets[key] = [key,_bucket[0],-1, {item[0]: ss_item}] # make new bucket, next = -1 as default

			if _bucket[2] != -1 : # prev.next not -1
				self.buckets[key][2] = _bucket[2] # update next on new bucket
				self.buckets[self.buckets[key][2]][1] = key

			self.buckets[_bucket[0]][2] = key
			self.elements[item[0]] = key
		else :
			#print "key exists update "
			self.elements[item[0]] = key
			self.buckets[key][3].update({item[0]:ss_item})

	def increase(self,item):
		#print "increase"
		_curr_key = self.elements[item[0]]
		_curr = self.buckets[_curr_key][3][item[0]]
		#print _curr
		new_weight = item[1] + _curr[1]
		new_key = int(math.ceil(new_weight))
		new_item = (item[0],new_weight, _curr[2])
		#print "new_item ", new_item
		if self.buckets.has_key(new_key) : # new bucket exists
			if (self.buckets[_curr_key][0] != new_key) :
				#print "new bucket exists. !Same key"
				self.elements[item[0]] = new_key # update map element -> bucket
				self.buckets[new_key][3].update({new_item[0]:new_item})
				self.buckets[_curr_key][3].pop(item[0]) # remove from old bucket
			else :
				#print "new bucket exists. Same key"
				self.buckets[new_key][3].update({item[0]:new_item})
		else:
			#print "!new bucket exists."
			_bucket = self.buckets[_curr_key]

			while _bucket[2] != -1 and self.buckets[_bucket[2]][0] < new_key :
				_bucket = self.buckets[_bucket[2]]

			self.buckets[new_key] = [new_key,_bucket[0],-1, {}]
#			self.buckets[new_key][3][item[0]] = new_item

			self.buckets[new_key][3].update({item[0]: new_item}) # insert increased item in new bucket
			if _bucket[2] != -1 : # found _bucket has next
				self.buckets[_bucket[2]][1] = new_key # set prev on
				self.buckets[new_key][2] = _bucket[2]

			self.buckets[_bucket[0]][2] = new_key
			self.elements[item[0]] = new_key
			self.buckets[_curr_key][3].pop(item[0])
			#self.min = self.buckets[self.min_bucket]

		if len(self.buckets[_curr_key][3]) == 0 :
			if _curr_key == self.min_bucket :
				self.min_bucket = self.buckets[_curr_key][2] # set new min to old mins next
				#print "min in bucket ", self.buckets[self.min_bucket][1]

				self.buckets[self.min_bucket][1] = -1
				self.delete_bucket_count += 1
			else :
				self.buckets[self.buckets[_curr_key][1]][2] = self.buckets[_curr_key][2]
				if self.buckets[_curr_key][2] != -1 :
					self.buckets[self.buckets[_curr_key][2]][1] =  self.buckets[_curr_key][1]
			del self.buckets[_curr_key]

	def get_min_el(self):
		#print "get min el "
		_min = self.buckets[self.min_bucket][3].values()[0]
		for item in self.buckets[self.min_bucket][3].values()[1:] :
			_curr_min = _min[1]
			_item_min = item[1]
			if _item_min < _curr_min :
				_min = item
		self.get_min_count += 1;
		return _min


	def replace_min(self,item):
		#print "replace min"
		_min = self.get_min_el()
		item_new = (item[0], item[1]+_min[1], _min[1])
		self.add_item(item_new)

		self.buckets[self.min_bucket][3].pop(_min[0])
		self.elements.pop(_min[0])

		if len(self.buckets[self.min_bucket][3]) == 0 :
			old_min = self.min_bucket
			#print "old_min ", old_min
			self.min_bucket = self.buckets[self.min_bucket][2] # new min is old.mins next
			#print "new min ", self.buckets[self.min_bucket]

			self.buckets[self.min_bucket][1] = -1

			del self.buckets[old_min]
			self.delete_bucket_count += 1

	def insert(self,item):
		if self.elements.has_key(item[0]) :
			self.increase(item)
			#print "self.min_bucket after\n", self.min_bucket
		elif len(self.elements) < self.k :
			self.add_item(item)
			#print "self.min_bucket after\n", self.min_bucket
		else :
			self.replace_min(item)
			#print "self.min_bucket after\n", self.min_bucket



def main():
	filename = 'input_zipf_1000000_1.5'
	data_dir = "../../data/"
	_input = pickle.load( open(data_dir +  filename) )
	#outstr = ""
	print "k\tavg\tgetmin\t|minbucket|\t#del min"
	#outstr += "k\tavg\tgetmin\t|minbucket|\t#del min\n"
#	_input = [((1,2),2),((1,2),1),((3,2),2),((3,2),2),((3,5),2),((5,2),2),((1,2),2),((3,4),2),((3,3),2)]
	for q in range(1,2) :
		N = math.pow(10, q)
		for i in range(1) :
			#k = int(math.pow(2, i) * N)
			k = 200

#			k = int(i * N)
			avg = 0.0
			it = 1
			for j in range(it) :
				hs = HashSummary(k)
				tracker = ClassTracker()
				tracker.track_class(HashSummary,resolution_level=2)
				tracker.track_object(hs,resolution_level=2)
				tracker.start_periodic_snapshots(interval=1)
				with util.Timer() as t :
					for _item in _input :
						hs.insert(_item)
				avg += t.interval
				#print "K: %s\t time: %.3f" % (k,t.interval)

			print "%s\t%.3f\t%s\t%s\t%s" % (k,avg/it,hs.get_min_count,len(hs.buckets[hs.min_bucket][3]),hs.delete_bucket_count)
			#outstr += "%s\t%.3f\t%s\t%s\t%s\n" % (k,avg/it,hs.get_min_count,len(hs.buckets[hs.min_bucket][3]),hs.delete_bucket_count)
#			print "%s\t%.3f" % (k, avg/3)
#			print "#get min: ", hs.get_min_count
#			print "size minbucket", len(hs.buckets[hs.min_bucket][3])
#			print "#del min: ", hs.delete_bucket_count
	#f = open('../out/hashsummary_4M-2.5.dat', 'w')
	#f.write(outstr)
	#f.close()
	print "#b:%d\te:%d\n" % (len(hs.buckets), len(hs.elements))
	print "time: %.3f\n" % t.interval
	#print hs.buckets

#	for _item in _input :
#		try :
#			hs.insert(_item)
#			#print hs.buckets
#		except Exception as e :
#			#print "ERROR"
#			#print e
#			#print hs.buckets
#
#			sys.exit(-1)
	tracker.stats.sort_stats('size').reverse_order().print_stats()
	#print hs.buckets

#print "self.elements", hs.elements

main()